package hyy_2022;

import java.util.Arrays;

public class _0803_136_SingleNumber {
    /**
     * 胡瑶瑶看官方题解后解题：
     * 1、先排序
     * 2、考虑特殊情况
     *          第一种特殊情况：只有一个元素,返回这个元素即可
     *          第二种特殊情况：如第一个元素与第二个元素不等,则第一个元素为只出现一次的元素
     *          第二种特殊情况：如最后一个移速与倒数第二个元素不等,则最后一个元素为只出现一次的元素
     *  3、普遍情况
     *          如果该元素既不等于前一个元素,也不等于后一个元素,则改元素为只出现一次的元素
     * @param nums  非空整数数组、除了某个元素只出现一次外,其他元素都出现两次
     * @return  查找在数组中只出现一次的元素
     */
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        int length = nums.length;
        if(length == 1 || nums[0] != nums[1] ) {
            return nums[0];
        }
        if(nums[length-1] != nums[length-2]) {
            return nums[length-1];
        }

        for(int i=1;i<length-1;i++) {
            if(nums[i-1] != nums[i]  && nums[i+1] != nums[i]) {
                return nums[i];
            }
        }
        return -1;
    }

    /**
     * 官方题解：位运算异或解题
     *  1、任何数和0做异或运算，结果仍然是原来的数
     *      0 ^ X = X
     *  2、任何数和自身做异或原酸，结果是0
     *      X ^ X = 0
     *  3、满足交换律和结合律
     *      X ^ Y ^ X = Y ^ X ^ X
     *      Y ^ X ^ X = Y ^ (x ^ X)
     *      Y ^ (x ^ X) = Y ^ 0 = Y
     * @param nums 非空整数数组、除了某个元素只出现一次外,其他元素都出现两次
     * @return 查找在数组中只出现一次的元素
     */
    public int singleNumber2(int[] nums) {
       int single = 0;
       for(int num : nums) {
           single ^= num;
       }
       return single;
    }

}
